package chapter16;

import java.util.Arrays;

/**
 * 贪心-找零钱问题
 */
public class Change {

    /**
     * 动态规划
     */
    public static int giveChange(int[] c, int m, int n) {
        int[][] counter = new int[m + 1][n + 1];
        int[][] f = new int[m + 1][n + 1];
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int k = i - 1;
                if (j < c[k]) {
                    f[i][j] = f[i - 1][j];
                    counter[i][j] = counter[i - 1][j];
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - c[k]] + c[k]);
                    counter[i][j] = Math.max(counter[i - 1][j], counter[i - 1][j - c[k]] + 1);
                    if (f[i][j] == n) {
                        min = Math.min(min, counter[i][j]);
                    }
                }
            }
        }
        System.out.println(Arrays.deepToString(f));
        System.out.println(Arrays.deepToString(counter));
        return f[m][n] == n ? min : -1;
    }

    public static int minCounter = Integer.MAX_VALUE;

    /**
     * 贪心
     */
    public static void giveChange(int[] c, int m, int n, int counter) {
        if (n < 0) {
            return;
        }
        if (n == 0) {
            minCounter = Math.min(minCounter, counter);
        }
        for (int i = 0; i < m; i++) {
            giveChange(c, m, n - c[i], counter + 1);
        }
    }

}
